/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.tree;

/**
 * <p>
 * 判断一个二叉树是否是平衡二叉树
 * 1.可以使用左右子树深度的方法
 * 2.可以直接递归
 * </p>
 * @author towan
 * @email tongwenzide@163.com 2015年5月18日
 */
public class BalancedBinaryTree {
    
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        int left = treeDepth(root.left);
        int right = treeDepth(root.right);
        if(Math.abs(left-right)>1){
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
     }

    /**
     * @param root
     * @return
     * @author towan
     * 2015年5月19日
     */
    private int treeDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left = treeDepth(root.left);
        int right = treeDepth(root.right);
        return 1+(left>right?left:right);
    }

    //不是通过深度方法，保证每次节点只遍历一次  FIXME
    public boolean isBalanced2(TreeNode root) {
       Integer depth = 0;
       return isBalanced(root, depth);
    }
    
    /**
     * @param root
     * @param depth
     * @return
     * @author towan
     * 2015年5月19日
     */
    private boolean isBalanced(TreeNode root, Integer depth) {
        if(root==null){
            depth =0;
            return true;
        }
        int left = 0 ,right = 0;
        if(isBalanced(root.left,left) && isBalanced(root.right,right)){
            int diff = left-right;
            if(Math.abs(diff)<=1){
                depth = 1+(left>right?left:right);
                return true;
            }
        }
        return false;
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode lRoot = new TreeNode(2);
        TreeNode rRoot = new TreeNode(3);
        root.left = lRoot;
        root.left = rRoot;
        
        lRoot.left = new TreeNode(4);
        lRoot.right = new TreeNode(5);
        lRoot.right.left = new TreeNode(7);
        
        rRoot.left = new TreeNode(6);
        
        BalancedBinaryTree bbTree = new BalancedBinaryTree();
        System.out.println(bbTree.isBalanced(root));
    }
    
    public static void main2(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(3);
        

        BalancedBinaryTree bbTree = new BalancedBinaryTree();
        System.out.println(bbTree.isBalanced(root));
    }

}
